A distributed data-parallel execution engine (DDPE engine or DDPEE)—such as Dryad, MapReduce, and Hadoop—provides a computation model that performs in parallel several independent sequential computations comprising subcomponents of a larger computation. However, in order to achieve necessary processing efficiencies, there are several requirements (or restrictions) common to these models. One requirement is that each subcomponent must run in a separate isolated address space for its complete lifetime. Another requirement is that data exchanges can only occur between each “round” of processing (since communications are expensive). Since a DDPE engine is generally used to process a large number of independent data items, these items must be grouped into relatively large batches (also referred to as partitions or shards) with a relatively uniform execution time per batch in order to ameliorate the expensive costs of communication and process creation/destruction. These several requirements, however, make it difficult to solve general optimization problems on a DDPE engine which typically require substantial communications between separate tasks, and especially in the communication of intermediate results.
A well-known approach to solving hard optimization problems is to traverse branch-and-bound (B&B) trees where the root of the tree is the original problem and the nodes stemming therefrom represent logical sub-problems that collectively correspond to the original problem to be solved. In the worst case scenario, the total number of nodes—which correspond to the problem size—can be exponentially large, and thus in practice the algorithms used with B&B trees attempt to resolve that certain branches of the tree cannot possibly contain the optimal solution and can therefore be pruned without negatively impacting the correctness of the solution. Even with pruning, however, seemingly small problems can lead to huge search trees, which are seemingly well-suited for a distributed execution approach where a cluster of computers could significantly reduce execution time. Nevertheless, existing B&B tree solvers are typically based on complex parallel computation frameworks that employ frequent communications between cluster machines, while DDPE engines have generally been deemed to be unsuited to these tasks because of their rigid requirements/restrictions regarding inter-machine communications.